/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package cs;

import java.util.Scanner;

/**
 *
 * @author QuangHieu
 */
// Su dung mang de cai dat
class Stack{
    int a[];
    int top;
    final int maxSize=1000;

    //tao ngan xep rong
    Stack(){
        a=new int[maxSize+1];
        top=0;
    }

    //kiem tra ngan xep rong
    boolean EmptyS(){
        if(top==0) return true;
        return false;
    }

    //them phan tu x vao dinh
    void Push(int x){
        if(top<maxSize)
            a[++top]=x;
        else System.out.print("\n Ngan xep day!\n");
    }

    //lay phan tu dau
    int PopS(){
        if(top==0){
            System.out.print("\nNgan xep rong!");
            return -1;
        }
        else return a[top--];
    }

    //tao stack
    void tao(){
        Scanner k=new Scanner(System.in);
        int x;int i=1;
        while(true){
            System.out.print("Nhap phan tu thu "+(i++));x=k.nextInt();
            if(x!=0) this.Push(x);
            else break;
        }
    }

    //xuat stack
    void xuat(){
        int x;
        Stack st=new Stack();
        while(!this.EmptyS()){
            x=this.PopS();
            System.out.print(x+" ");
            st.Push(x);
        }
        while(!st.EmptyS())
            this.Push(st.PopS());
    }

    //lay phan tu thu k
    int remove(int k) {
        Stack st = new Stack();
        int i = 1;
        int x;
        if (k < 1) {
            System.out.print("Vi tri qua nho");
            return -1;
        } else {
            while (i < k && !this.EmptyS()) {
                x = this.PopS();
                st.Push(x);
                i++;
            }
            if (i == k) {
                x = this.PopS();
                while (!st.EmptyS()) {
                    this.Push(st.PopS());
                }
                return x;
            } else {
                System.out.print("\n" + k + " vuot qua so phan tu stack!");
                return -1;
            }
        }
    }

    //them x vao vi tri thu k
    int add(int x, int k) {
        Stack st = new Stack();
        int i = 1;
        int a;
        if (k < 1) {
            System.out.print("Vi tri qua nho");
            return -1;
        } else {
            while (i < k && !this.EmptyS()) {
                a = this.PopS();
                st.Push(a);
                i++;
            }
            if (i == k) {
                this.Push(x);
                while (!st.EmptyS()) {
                    this.Push(st.PopS());
                }
                return x;
            } else {
                System.out.print("\n" + k + " vuot qua so phan tu stack!");
                return -1;
            }
        }
    }

    //xoa cac so le
    void RemoveOdd(){
        Stack st=new Stack();
        while(!this.EmptyS()){
            if(top%2!=0)
                this.PopS();
            else st.Push(this.PopS());
        }
        while(!st.EmptyS())
            this.Push(st.PopS());
    }

    //dao stack
    void daoStack(){

    }
    /*
    public static void main(String args[]){
        Stack s=new Stack();
        for(int i=1;i<10;i++) s.Push(i);
        System.out.print("\n Noi dung ngan xep: ");
        while(!s.EmptyS())
            System.out.print(s.PopS() +" ");
        s.tao();
        s.remove(4);
        s.xuat();
    }*/
}


class Node{
    int data;
    Node next;

    Node(int x){
        data=x;
        next=null;
    }
    Node(int x, Node t){
        data=x;
        next=t;
    }
}

class Stack1{
    Node top;

    Stack1(){
        top=null;
    }

    boolean EmptyS(){
        return top==null;
    }

    void pushS(int x){
        top=new Node(x,top);
    }

    int popS(){
        if(top==null){
            System.out.print("\nStack rong\n");
            return -1;
        }
        else {
            int x=top.data;
            top=top.next;
            return x;
        }
    }

    void tao(){
        Scanner k=new Scanner(System.in);
        int x;int i=1;
        while(true){
            System.out.print("Nhap phan tu thu "+(i++));x=k.nextInt();
            if(x!=0) this.pushS(x);
            else break;
        }
    }

    //xuat stack
    void xuat(){
        int x;
        Stack1 st=new Stack1();
        while(!this.EmptyS()){
            x=this.popS();
            System.out.print(x+" ");
            st.pushS(x);
        }
        while(!st.EmptyS())
            this.pushS(st.popS());
    }

    //lay phan tu thu k
    int remove(int k) {
        Stack1 st = new Stack1();
        int i = 1;
        int x;
        if (k < 1) {
            System.out.print("Vi tri qua nho");
            return -1;
        } else {
            while (i < k && !this.EmptyS()) {
                x = this.popS();
                st.pushS(x);
                i++;
            }
            if (i == k) {
                x = this.popS();
                while (!st.EmptyS()) {
                    this.pushS(st.popS());
                }
                return x;
            } else {
                System.out.print("\n" + k + " vuot qua so phan tu stack!");
                return -1;
            }
        }
    }

    //them x vao vi tri thu k
    int add(int x, int k) {
        Stack1 st = new Stack1();
        int i = 1;
        int a;
        if (k < 1) {
            System.out.print("Vi tri qua nho");
            return -1;
        } else {
            while (i < k && !this.EmptyS()) {
                a = this.popS();
                st.pushS(a);
                i++;
            }
            if (i == k) {
                this.pushS(x);
                while (!st.EmptyS()) {
                    this.pushS(st.popS());
                }
                return x;
            } else {
                System.out.print("\n" + k + " vuot qua so phan tu stack!");
                return -1;
            }
        }
    }
    public static void main(String args[]){
        Stack1 s=new Stack1();

    }
}

public class MyStack {

}
